package 中等.队列;

import java.util.PriorityQueue;

/**
 * 你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 
 * 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半
 * 过的数继续执行操作）
 * 请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-operations-to-halve-array-sum
 */
public class 将数组和减半的最少操作数_2208 {

    public static void main(String[] args) {

        int[] nums = {5, 19, 8, 1};
        System.out.println(halveArray(nums));

    }

    /**
     * 贪心思想+优先队列
     *
     * @param nums
     * @return
     */
    public static int halveArray(int[] nums) {
        double sum = 0;
        PriorityQueue<Double> priorityQueue = new PriorityQueue<>(nums.length,
                (o1, o2) -> o2 - o1 > 0 ? 1 : -1);
        for (int num : nums) {
            sum += num;
            priorityQueue.add((double) num);
        }
        int count = 0;
        double curSum = 0, targetSum = sum / 2;
        while (curSum < targetSum) {
            Double num = priorityQueue.poll();
            priorityQueue.add(num / 2);
            curSum += num / 2;
            count++;
        }
        return count;
    }

}
